package letcode.oneQuestionPerDay._202003._20200302;

import letcode.util.ListNode;

/*
反转链表   递归
 */
public class ReverseLinkedList_2 {
    public static void main(String[] args) {
        
        ListNode oldhead=new ListNode(1);
        oldhead.next=new ListNode(2);
        oldhead.next.next=new ListNode(3);
        oldhead.next.next.next=new ListNode(4);
        oldhead.next.next.next.next=new ListNode(5);

        ListNode head=reverseList(oldhead);
        System.out.println(head.val);
        System.out.println(head.next.val);
        System.out.println(head.next.next.val);
        System.out.println(head.next.next.next.val);
        System.out.println(head.next.next.next.next.val);
    }
    //提供方法
    public static ListNode reverseList(ListNode head) {
        //从n1。。。nk-1、nk、nk+1。。。nm。假设nk+1到nm已经完成反转了。则nk.next.next=nk.注意到n1的时候next=null
        if (head==null||head.next==null)
            return head;
        ListNode curr=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return curr;
    }
}

/*
反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 */